import java.util.Arrays;
import java.util.Map;

class text{
    public static void main(String[] args) {
        dynamic_programming t = new dynamic_programming();
        int[] arr = {10,9,2,5,3,7,101,18};
        System.out.println(t.lengthOfLIS(arr));
    }
}

/**
 * 使用dp数组来记录在每个下标下的最长的有序数组
 * 每次找最长的就在当前下标i下遍历i-1次dp数组，找到最长的且结尾小于当前i的
 * 解决
 */
public class dynamic_programming {
    //最长有序数列
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        //dp[i]表示的是改下标结尾最长的序列
        Arrays.fill(dp, 1);
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int max = 1;//这里是i位置下最大的有序数组
//            boolean flg = false;
            for (int j = 0; j < i; j++) {//遍历dp 0 ~ i-1
                if (nums[j] < nums[i]) {//j结尾的最长的且是小于i的才能加一
//                    max = Math.max(dp[j], max);
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
//                    flg = true;
                }
            }
//            if (flg) {
//                max+=1;
//            }
//            dp[i] = max;
            ret = Math.max(ret, dp[i]);
        }
        //在dp中返回最大的长度
//        int max = 0;
//        for (int i = 0; i < n; i++) {
//            max = Math.max(max, dp[i]);
//        }
        return ret;
    }
}
